package lc.daily;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 2022年4月打卡题目
 */
public interface Y22M04 {

    /**
     * 796. 旋转字符串
     * <p>
     * <p>
     * 给定两个字符串, s和goal。如果在若干次旋转操作之后，s能变成goal，那么返回true。
     * <p>
     * s的 旋转操作 就是将s 最左边的字符移动到最右边。
     * 例如,
     * <ul>
     *     <li>若s = 'abcde'，在旋转一次之后结果就是'bcdea'。</li>
     * </ul>
     * <p>
     * 提示:
     * <ul>
     *     <li>1 <= s.length, goal.length <= 100</li>
     *     <li>s 和 goal 由小写英文字母组成</li>
     * </ul>
     *
     * @param s
     * @param goal
     * @return
     */
    boolean rotateString(String s, String goal);

    class Node {
        public int val;
        public List<Node> children;

        public Node() {

        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    /**
     * 429. N 叉树的层序遍历
     * <p>
     * <p>
     * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
     * <p>
     * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔
     * <p>
     * 提示：
     * <ul>
     *     <li>树的高度不会超过 1000</li>
     *     <li>树的节点总数在 [0, 10<sup>4</sup>] 之间</li>
     * </ul>
     *
     * @param root
     * @return
     */
    List<List<Integer>> levelOrder(Node root);

    /**
     * 780. 到达终点
     * <p>
     * <p>
     * 给定四个整数sx,sy，tx和ty，如果通过一系列的转换可以从起点(sx, sy)到达终点(tx, ty)，则返回 true，否则返回false。
     * <p>
     * 从点(x, y)可以转换到(x, x+y) 或者(x+y, y)。
     * <p>
     * 提示:
     * <ul>
     *     <li>1 <= sx, sy, tx, ty <= 10<sup>9</sup></li>
     * </ul>
     *
     * @param sx
     * @param sy
     * @param tx
     * @param ty
     * @return
     */
    boolean reachingPoints(int sx, int sy, int tx, int ty);

    /**
     * 804. 唯一摩尔斯密码词
     * <p>
     * <p>
     * 国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串，比如:
     * <ul>
     *     <li>'a' 对应 ".-"</li>
     *     <li>'b' 对应 "-..."</li>
     *     <li>'c' 对应 "-.-." ，以此类推。</li>
     * </ul>
     * <p>
     * 为了方便，所有 26 个英文字母的摩尔斯密码表如下：
     * <p>
     * [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
     * <p>
     * <p>
     * 给你一个字符串数组 words ，每个单词可以写成每个字母对应摩尔斯密码的组合。
     * <p>
     * 例如，"cab" 可以写成 "-.-..--..." ，(即 "-.-." + ".-" + "-..." 字符串的结合)。我们将这样一个连接过程称作 单词翻译 。
     * 对 words 中所有单词进行单词翻译，返回不同 单词翻译 的数量。
     * <p>
     * 提示：
     * <ul>
     *     <li>1 <= words.length <= 100</li>
     *     <li>1 <= words[i].length <= 12</li>
     *     <li>words[i] 由小写英文字母组成</li>
     * </ul>
     *
     * @param words
     * @return
     */
    int uniqueMorseRepresentations(String[] words);

    /**
     * 357. 统计各位数字都不同的数字个数
     * <p>
     * <p>
     * 给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10<sup>n</sup> 。
     *
     * @param n 0 <= n <= 8
     * @return
     */
    int countNumbersWithUniqueDigits(int n);

    /**
     * 806. 写字符串需要的行数
     * <p>
     * <p>
     * 我们要把给定的字符串 S从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组widths，这个数组widths[0] 代表 'a' 需要的单位，widths[1] 代表 'b' 需要的单位，...，widths[25] 代表 'z' 需要的单位。
     * <p>
     * 现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。
     * <p>
     *
     * <ul>
     *     <li>字符串S 的长度在[1, 1000] 的范围。</li>
     *     <li>S 只包含小写字母。</li>
     *     <li>widths 是长度为26的数组。</li>
     *     <li>widths[i]值的范围在[2, 10]。</li>
     * </ul>
     *
     * @param widths
     * @param s
     * @return [总行数, 最后一行的宽度]
     */
    int[] numberOfLines(int[] widths, String s);

    interface RandomizedSet {

        /**
         * @param val
         * @return 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
         */
        boolean insert(int val);

        /**
         * @param val
         * @return 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false。
         */
        boolean remove(int val);

        /**
         * @return 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
         */
        int getRandom();
    }

    /**
     * 380. O(1) 时间插入、删除和获取随机元素
     *
     * <p>
     * 实现RandomizedSet 类：
     * <ul>
     *     <li>RandomizedSet() 初始化 RandomizedSet 对象</li>
     *     <li>bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。</li>
     *     <li>bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。</li>
     *     <li>int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。</li>
     * </ul>
     * 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
     * <p>
     * 提示：
     * <ul>
     *     <li>-2<sup>31</sup> <= val <= 2<sup>31</sup> - 1</li>
     *     <li>最多调用 insert、remove 和 getRandom 函数 2 *10<sup>5</sup> 次</li>
     *     <li>在调用 getRandom 方法时，数据结构中 至少存在一个 元素。</li>
     * </ul>
     */
    RandomizedSet randomizedSet();

    /**
     * 1672. 最富有客户的资产总量
     * <p>
     * <p>
     * 给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。
     * <p>
     * 客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
     * <p>
     * 提示：
     *
     * <ul>
     *     <li>m ==accounts.length</li>
     *     <li>n ==accounts[i].length</li>
     *     <li>1 <= m, n <= 50</li>
     *     <li>1 <= accounts[i][j] <= 100</li>
     * </ul>
     *
     * @param accounts
     * @return
     */
    int maximumWealth(int[][] accounts);

    /**
     * 385. 迷你语法分析器
     * <p>
     * <p>
     * 给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果NestedInteger 。
     * <p>
     * 列表中的每个元素只可能是整数或整数嵌套列表
     * <p>
     * 提示：
     * <ul>
     *     <li>1 <= s.length <= 5 * 10<sup>4</sup></li>
     *     <li>s 由数字、方括号"[]"、负号'-'、逗号','组成</li>
     *     <li>用例保证s 是可解析的NestedInteger</li>
     *     <li>输入中的所有值的范围是[-10<sup>6</sup>, 10<sup>6</sup>]</li>
     * </ul>
     *
     * @param s
     * @return
     */
    NestedInteger deserialize(String s);

    class NestedInteger {

        private Integer integer;

        private List<NestedInteger> list;

        public NestedInteger() {
        }

        public NestedInteger(int value) {
            this.integer = value;
        }

        /**
         * @return true if this NestedInteger holds a single integer, rather than a nested list.
         */
        public boolean isInteger() {
            return list == null || list.isEmpty();
        }

        /**
         * @return the single integer that this NestedInteger holds, if it holds a single integer
         * Return null if this NestedInteger holds a nested list
         */
        public Integer getInteger() {
            return this.integer;
        }

        /**
         * Set this NestedInteger to hold a single integer.
         */
        public void setInteger(int value) {
            this.integer = value;
        }

        /**
         * Set this NestedInteger to hold a nested list and adds a nested integer to it.
         */
        public void add(NestedInteger ni) {
            if (list == null) list = new ArrayList<>();
            list.add(ni);
        }

        /**
         * @return the nested list that this NestedInteger holds, if it holds a nested list
         * Return empty list if this NestedInteger holds a single integer
         */
        public List<NestedInteger> getList() {
            return list == null ? Collections.emptyList() : new ArrayList<>(list);
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            if (integer != null) builder.append(integer);

            if (!isInteger()) {
                builder.append(",");
                for (NestedInteger value : list) {
                    builder.append("[")
                            .append(value)
                            .append("]");
                }
            }

            return builder.toString();
        }
    }

    /**
     * 479. 最大回文数乘积
     * <p>
     * <p>
     * 给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余
     * <p>
     * 提示
     * <ul>
     *     <li>1 <= n <= 8</li>
     * </ul>
     *
     * @param n
     * @return
     */
    int largestPalindrome(int n);

    /**
     * 819. 最常见的单词
     * <p>
     * <p>
     * 给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。
     * <p>
     * 题目保证至少有一个词不在禁用列表中，而且答案唯一。
     * <p>
     * 禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。
     * <p>
     * <p>
     * 提示：
     *
     * <ul>
     *     <li>1 <= 段落长度 <= 1000</li>
     *     <li>0 <= 禁用单词个数 <= 100</li>
     *     <li>1 <= 禁用单词长度 <= 10</li>
     *     <li>答案是唯一的, 且都是小写字母(即使在 paragraph 里是大写的，即使是一些特定的名词，答案都是小写的。)</li>
     *     <li>paragraph只包含字母、空格和下列标点符号!?',;.</li>
     *     <li>不存在没有连字符或者带有连字符的单词。</li>
     *     <li>单词里只包含字母，不会出现省略号或者其他标点符号。</li>
     * </ul>
     *
     * @param paragraph
     * @param banned
     * @return
     */
    String mostCommonWord(String paragraph, String[] banned);

    /**
     * 386. 字典序排数
     * <p>
     * <p>
     * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
     * <p>
     * 你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
     *
     * @param n 1 <= n <= 5 * 10<sup>4</sup>
     * @return
     */
    List<Integer> lexicalOrder(int n);

    /**
     * 821. 字符的最短距离
     * <p>
     * <p>
     * 给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
     * <p>
     * 返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
     * <p>
     * 两个下标i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。
     * <p>
     * 提示：
     * <ul>
     *     <li>1 <= s.length <= 10<sup>4</sup></li>
     *     <li>s[i] 和 c 均为小写英文字母</li>
     *     <li>题目数据保证 c 在 s 中至少出现一次</li>
     * </ul>
     *
     * @param s
     * @param c
     * @return
     */
    int[] shortestToChar(String s, char c);

    /**
     * 388. 文件的最长绝对路径
     * <p>
     * <p>
     * 假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：
     * <p>
     * <img src='https://assets.leetcode.com/uploads/2020/08/28/mdir.jpg' />
     * <p>
     * 这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。subdir1 包含文件 file1.ext 和子目录 subsubdir1；subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。
     * <p>
     * 在文本格式中，如下所示(⟶表示制表符)：
     * <p>
     * dir<br />
     * ⟶ subdir1<br />
     * ⟶ ⟶ file1.ext<br />
     * ⟶ ⟶ subsubdir1<br />
     * ⟶ subdir2<br />
     * ⟶ ⟶ subsubdir2<br />
     * ⟶ ⟶ ⟶ file2.ext<br />
     * <p>
     * 如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。'\n' 和 '\t' 分别是换行符和制表符。
     * <p>
     * 文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。上面例子中，指向 file2.ext 的 绝对路径 是 "dir/subdir2/subsubdir2/file2.ext" 。每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，其中name和extension由字母、数字和/或空格组成。
     * <p>
     * 给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中指向文件的 最长绝对路径 的长度。 如果系统中没有文件，返回0。
     * <p>
     * 提示：
     * <ul>
     *     <li>1 <= input.length <= 10<sup>4</sup></li>
     *     <li>input 可能包含小写或大写的英文字母，一个换行符 '\n'，一个制表符 '\t'，一个点 '.'，一个空格 ' '，和数字。</li>
     * </ul>
     *
     * @param input
     * @return
     */
    int lengthLongestPath(String input);

    /**
     * 824. 山羊拉丁文
     * <p>
     * <p>
     * 给你一个由若干单词组成的句子sentence ，单词间由空格分隔。每个单词仅由大写和小写英文字母组成。
     * <p>
     * 请你将句子转换为 “山羊拉丁文（Goat Latin）”（一种类似于 猪拉丁文- Pig Latin 的虚构语言）。山羊拉丁文的规则如下：
     * <ul>
     *     <li>
     *         如果单词以元音开头（'a', 'e', 'i', 'o', 'u'），在单词后添加"ma"。
     *         <ul>
     *             <li>例如，单词 "apple" 变为 "applema" 。</li>
     *         </ul>
     *     </li>
     *     <li>
     *         如果单词以辅音字母开头（即，非元音字母），移除第一个字符并将它放到末尾，之后再添加"ma"。
     *         <ul>
     *             <li>例如，单词 "goat" 变为 "oatgma" 。</li>
     *         </ul>
     *     </li>
     *     <li>
     *         根据单词在句子中的索引，在单词最后添加与索引相同数量的字母'a'，索引从 1 开始。
     *         <ul>
     *             <li>例如，在第一个单词后添加 "a" ，在第二个单词后添加 "aa" ，以此类推。</li>
     *         </ul>
     *     </li>
     * </ul>
     * 返回将 sentence 转换为山羊拉丁文后的句子。
     * <p>
     * 提示：
     * <ul>
     *     <li>1 <= sentence.length <= 150</li>
     *     <li>sentence 由英文字母和空格组成</li>
     *     <li>sentence 不含前导或尾随空格</li>
     *     <li>sentence 中的所有单词由单个空格分隔</li>
     * </ul>
     *
     * @param sentence
     * @return
     */
    String toGoatLatin(String sentence);

    /**
     * 396. 旋转函数
     * <p>
     * <p>
     * 给定一个长度为 n 的整数数组nums。
     * <p>
     * 假设arr<sub>k</sub>是数组nums顺时针旋转 k 个位置后的数组，我们定义nums的 <b>旋转函数</b> F为：
     *
     * <ul>
     *     <li>F(k) = 0 * arr<sub>k</sub>[0] + 1 * arr<sub>k</sub>[1] + ... + (n - 1) * arr<sub>k</sub>[n - 1]</li>
     * </ul>
     * 返回F(0), F(1), ..., F(n-1)中的最大值。
     * <p>
     * 生成的测试用例让答案符合32 位 整数。
     * <p>
     * <p>
     * 提示:
     * <ul>
     *     <li>n == nums.length</li>
     *     <li>1 <= n <= 10<sup>5</sup></li>
     *     <li>-100 <= nums[i] <= 100</li>
     * </ul>
     *
     * @param nums
     * @return
     */
    int maxRotateFunction(int[] nums);

    /**
     * 587. 安装栅栏
     * <p>
     * <p>
     * 在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。
     * <p>
     * 注意:
     * <ul>
     *     <li>所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。</li>
     *     <li>输入的整数在 0 到 100 之间。</li>
     *     <li>花园至少有一棵树。</li>
     *     <li>所有树的坐标都是不同的。</li>
     *     <li>输入的点没有顺序。输出顺序也没有要求。</li>
     * </ul>
     *
     * @param trees
     * @return
     */
    int[][] outerTrees(int[][] trees);

    /**
     * 868. 二进制间距
     * <p>
     * <p>
     * 给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。
     * <p>
     * 如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。
     * <p>
     * 提示：
     * <ul>
     *     <li>1 <= n <= 10<sup>9</sup></li>
     * </ul>
     *
     * @param n
     * @return
     */
    int binaryGap(int n);
}
